//倍增求解 时间复杂度 O(nlogn) 每次查询的时间复杂度O(mlogn)属于在线算法
int fa[N][25];
int depth[N];
void bfs(int root)
{
    memset(depth,0x3f,sizeof depth);
    depth[0] = 0;//如果我们不设置depth[0] = 0 
    //那么在从i开始跳出根节点的时候 depth[fa[i][j]]] = 0x3f3f3f3f 
    depth[root] = 1;
    queue<int>q;
    q.push(root);
    while(q.size())
    {
        int t = q.front();
        q.pop();
        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(depth[j] > depth[t] + 1)//更新深度
            {
                depth[j] = depth[t] + 1;
                q.push(j);
                fa[j][0] = t;//倍增更新父子关系
                for(int k = 1; k <= 22; k ++)//2的22次方
                {
                    fa[j][k] = fa[fa[j][k - 1]][k - 1];//递推 进入下一个状态
                    //意思是f的2^i祖先等于f的2^(i-1)祖先的2^(i-1)祖先
					//2^i=2^(i-1)+2^(i-1)
                }
            }
        }
    }
}

void dfs (int x, int fas)
{
	depth[x] = depth[fas] + 1;
	fa[x][0] = fas;
	for(int i = 1; i <= 20; i++) {
		fa[x][i] = fa[fa[x][i - 1]][i - 1];
	}
    for(int i = h[x]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(j == fas) continue;
        dfs(j,x);
    }
}
int lca(int a,int b)
{
    if(depth[a] < depth[b]) swap(a,b);
    for(int k = 22; k >= 0; k --)
    {
        if(depth[fa[a][k]] >= depth[b])
            a = fa[a][k];
    }
    if(a == b) return a;
    for(int k = 22; k >= 0; k --)
    {
        if(fa[a][k] != fa[b][k])
        {
            a = fa[a][k];
            b = fa[b][k];
        }
    }
    return fa[a][0];
}
//tanjan算法,需要把m个询问一次性读入 统一计算 最后统一输出 时间复杂度为O(n + m),离线来求LCA的距离
//两个节点(x, y)的树上距离实际上就是 d[x]+d[y]−2*d[F[x,y]]  (F[x, y] 表示x y的最近公共祖先节点)
int dist[N];
int p[N];
int res[M];
int st[N];
int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}
void dfs(int u, int fa)
{
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == fa) continue;
        dist[j] = dist[u] + w[i];
        dfs(j, u);
    }
}
vector<PII> query[N];  // first 存查询的另外一个点 second 存查询编号
void tarjan(int u) //当前节点的编号为u
{
    st[u] = 1;//当前的点是第二类点
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            tarjan(j);
            p[j] = u; // 更新节点信息
        }
    }
    for (auto item : query[u]) //遍历每个涉及节点U的情况
    {
        int y = item.first, id = item.second;
        if (st[y] == 2) //如果y是已经标记并且回溯过 则直接输出
        {
            int anc = find(y);
           // 存储相应的结果用来输出
            res[id] = dist[u] + dist[y] - dist[anc] * 2;
        }
    }
    st[u] = 2; //对当前点进行标记
}
for (int i = 0; i < m; i ++ )
{
    int a, b;
    scanf("%d%d", &a, &b);
    if (a != b)
    {
        query[a].push_back({b, i});
        query[b].push_back({a, i});
    }
}
for (int i = 1; i <= n; i ++ ) p[i] = i;
dfs(1, -1);
tarjan(1);
for (int i = 0; i < m; i ++ ) printf("%d\n", res[i]);
